{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 随机梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1,1)\n",
    "y = 4.*x + 3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3W2MXNd5H/D/M8NLaVZuOUtonUgjUiQEhYxURtxqLAveDzXllLRDS9pIlhnVCgwkgL4kQMgqbJexYFKpDC1AVFLRBmjVNqgLyvIyoTymQwf0C1kUIELWu96laUJkI1vUSkM22pgc2eIOydnd0w8zd3hn9r7O3Pf7/wGGtbOzcw+Hy2fOfc5zniNKKRARUfrloh4AERGFgwGfiCgjGPCJiDKCAZ+IKCMY8ImIMoIBn4goIxjwiYgyggGfiCgjGPCJiDJiRdQDMLr99tvVunXroh4GEVGiTE1N/aNSasjpebEK+OvWrcPk5GTUwyAiShQRedfN85jSISLKCAZ8IqKMYMAnIsoIBnwiooxgwCciyohYVekQESVFZbqK/UfP42KtjjuLBezetgGjw6Woh2WLAZ+IyKPKdBV73jyDemMRAFCt1bHnzTMAEOugz5QOEZFH+4+ebwd7Xb2xiP1Hz0c0IncY8ImIPLpYq3t6PC4Y8ImIPLqzWPD0eFww4BMRebR72wYUtHzHYwUtj93bNkQ0Ine4aEtE5JG+MMsqHSKiDBgdLsU+wHdjwCci30VZo2537STWzvtJlFJRj6GtXC4rtkcmSrbuGnWgmd9+6YlNgQdXs2sLAAVgcEDDR9cW0Fi6GfPCGlfQRGRKKVV2eh4XbYnIV0HUqFemqxgZP4b1Y0cwMn4Mlemq62vr4f3KfKMj2PsxrqRhSoeIOvSb9vC7Rt3LrtZerhH32nk/MeATUZsfLQPuLBZQNQmieo261w8UpzsG42sVBzRcmW+4GqfTuLZsHMLxc3Opyvczh09EbSPjx0yDdalYwImxR1y9hl0OH4Dn/P76sSOwilIFLd/xWlpOAAEai+7imt24rJ7rNeiHsVDMHD4ReeZHOmZ0uISXntiEUrEAQfPDQg+UveT3rXav5kWWvVZjSUHQXKg1o+UFxYLWHteTDzbHtHNixjbYuxmnGf3Dr1qrQ+HmHZPVGkTQmNIhojandIxbVjXqvXyg7N62wbTyZtEiO3HDYnafF8H+LzzQUaLpNKv3Mk4zdh9wUaSHOMMnoragWwasKmiOj3dX5ADAS09sQtHwnF4S0UtKdQTZfYfPegr2gPcPvrg1WeMMn4jagm4ZIBa5Fv1xq0XjJx8s4frCUl/XNgbrynQVtbq3xd2ClseWjUMYGT/m+N7oeXurD6aomqz1HfBFZA2A/wng1wEsAXhNKfUfRGQ1gAkA6wBcAPBFpdSVfq9HRMHy2jLAy6JkzaKCpjbfQGW6iucOnl6Wqqk3FvHGqfcsUzhm9M1Wuu67lBe+c9b1awFAToAnHyzh0FTVsYLJKVUUZZM1P1I6CwCeU0r9JoCHAfyRiNwHYAzAD5VS9wL4YetrIkoRs0XJXRMzeL5yxvT5VjPb4oCGPW+esQzqXoJ9Pie4VbsZ2gYHtI7qmsp01XPpplLA8XNzrhaczfL2OuMCdhT6nuErpS4BuNT671+JyFsASgAeB/Dp1tO+DuB/Afi3/V6PiOLDamfr6ydnUb57NYDmbFoPsAUtBy0vHWWTBS0PpeA5n25lcUmhbthRe63RmQrqZWftncWC63y81fMEcF3aGhRfc/gisg7AMIBTAH6t9WEApdQlEfm4n9ciIn+4SclYPccquCkAuw7OICeCRUPwrbeCb06AJdWsnHnywRJePzkb2J+vuyrG64Kplhfs3rYB+4+ed1XB5FelUxB8q9IRkY8BOARgp1Lqlx5+7lkRmRSRybm5Ob+GQ0QuuKkTN3vOzokZDP/591AcMK+6AZppkMUl81SM/vCiUjhwctZz1U2pWMAzD691/XxjkDeme9zY8Yk17WDfveYsALZsHOp4LM6Ho/gS8EVEQzPYv66UerP18D+IyB2t798B4AOzn1VKvaaUKiulykNDQ2ZPIaKAuNkIZZWTvjLfwEfXFgIfY7fB1ofMAQ93BQrNXcTPV8607zLcXuvQVLU9Y+/+YFIADk1VOz4g7TaeRc2PKh0B8N8BvKWUetnwrcMAvgxgvPX/3+73WkTkL6v0hjElYZae0HV3nwzDlfmG50VXoPnn8JI6cru2YLaRKq6Ho/iRwx8B8PsAzojITOuxP0Mz0B8UkT8EMAvgKR+uRUQ+sso3C9CetXaXOIbNz+u7fZ1Sa51i18SM85PRXyfQMA9kYfM0ogyrTFexa2LGNBDmRTyVQ6aF/ucuFQuYv7Hg6m7CS3M5nZ8HxbhtnsadtkQpZTZ7BJbvorUK6W6CfdSz/yDof267VJZRrwuyUfTZYcAnSiGzFgW7//o0oG7m3fWKnMEeesgD2bwDEACfumc1Lvyi3ncaJoo+Owz4RClj1aLArEd8vbGIW1bklvWVdyNrwR5o3s1c+EW95w1UxruunMUHZpD1+gz4RCmiz+y9BONavWHZP56W8+uoRrO/o6Dr9RnwiRKuMl3taF/Qi+zN1XuXE0Fluuo6jaPP6q3WBPIiWFIqlCodBnyiBHu+csbTBiTq36JSrs/5dXPIypJSeGd8u69jtMIDUIgSqjJdZbCPiNvjDu06Z+rC7LHDGT6RC71ukAliY83zlTOe+8OT/6q1uuNhKE75/rB77DDgEzmwOoUJsL+l7/Xn7DCFEx+Cm7X6Vn+3VjuZdWH32GFKh8iBmwZjfv6cnTdOvdfzz5K/uu+vzP5ud2/bYFkBVSoWQu+3wxk+kYNeN8hYzez0nzOme4oDGpQCPqw3bFM/TOPEW/fvxOhwCZPvXsbrXS2go2qXzBk+kQOrRbWcCNaPHcHI+LGO9rhAM5hbzezuLBaW9Zi/Mt9Ard6w7EkPwPLYQIoPs9+VF0c34ZUdm2PRLpkzfCIHu7dtMC2tM/Zc6c7f7j963rS2XVqv51S9UW8s4rmDp9uvWZmuBnoqFPXPbtYel3bJnOETOeg+0CIvy+fu3flbu6P/7I4GNFpUCrsmZvCl//p3lh0tKXpRz9q94AyfyAXjDG392BHT5xiDuFV1Rql1y7+qoKFWd94ZqwCc+NnlHkZMYSgWNMzs3dpej9k1MRPKjtlecYZP5JFVTl8/Rq8yXTU911Q//7QyXcWvrod/NCD5T8TducBxwYBP5FJluoqR8WOmh1nrjPn8f752Vcf3FIBvnJrFzokZy8O9KVlq841Aym+DwpQOkQvdm6gUrA//qDcWse/wWXxokrJhnI83LS+4beUK1OqNjpOvrl5fME3B3VksRNLXvlcM+JRafrY1MJvF2cVuN/l5ipecADs+sQYvjm5a9j2r4wj1iiuz9Zowe+S4xZQOpZLfedU4ztbIX0sKmPjRe6a/I92VWsaqHLP1mqg2VjnhIeaUSnquvVsvh03bvV6xoOH6wpLn06Io3koe7wiDaJLnBQ8xp0zzI6/a3fpAy0n7PFgA0HICETDYp1C1Vsfuv7q58c3IKrjHsQyzGwM+pZJVHbybvKrZCVJX5hvQ8oJiQcOH9QZWFTT88lqjr1OmKN4aSwr7Dp/tCORBdEANEwM+pZJZOwSrvKpxxraqoOHqjQXTA78biwq/uraAV3Zsxr7DZ1lxkwHdi+92JZgM+EQRMfa0qdbqyIu0+9PsnJhp52gBdHwwOFXX6MfbMY2TTUkqwTTDgE+ppQd9Y4Dubnh2y4qc5+DNYJ8dgwNax9f9pArjgGWZlGp2XSnrjUXWy5OtvY/e3/F1kkowzTDgU6ol5Vab4kUAPPPwWgDNklz93AMAlvX4ScCUDqWa05migwMarjVYR083Wa3v6GnAl57Y1NNejjjgDJ9SzewW3OjGwhKEneapZXBAw4mxRzA6XEpUUzS3GPAp1Yxb4gEs63J59cYi5htL4Q+MYumjawvt1gpOZxInEVM6lHr6LsjKdBX/+uAMYtRNhGKmsaTaM3irbqhJqcgxwxk+ZYK+Q5KbpcjJxVrd8UzipOIMnxKlu4/Jlo1DOH5urt3vRingw3pjWQMrp0PDiXR2Pe71M4mTijN8SgyzlscHTs62v74y30Ct3jBth5zkvCuFRz+G0iptkxeJ5dGFbjHgU2J4naUbKyqSnHel8CgAh6aq2LJxyLS6S2+tkdSgz4BPiWFXT2/3M+vHjvT0s5RN9cYijp+bw0tPbEJelp9enOTSTAZ8SoTKdNXy4HAnXKclry7W6hgdLmHJoqQrqSlCXwK+iPyliHwgIj81PLZaRL4vIn/f+v9BP65F2WRVNUEUBD0FaJUKTGqK0K8Z/v8A8Nmux8YA/FApdS+AH7a+JupJUmdUlDzGZmhJb5bWzZeAr5T63wAudz38OICvt/776wBG/bgWZU9luoqcSS6VyC95EdNmaHaHlydRkHX4v6aUugQASqlLIvLxAK9FKWR21CCR3wpa3jaIJ+W8Wjci33glIs8CeBYA1q5dG/FoKAxWh0Abv1et1S23thP5JS+S6Bm7V0EG/H8QkTtas/s7AHxg9iSl1GsAXgOAcrnMf98pZ3cINNDZjpa/DBS0JaUyE+yBYAP+YQBfBjDe+v9vB3gtSginlrNsf0BhSmq1Ta98Cfgi8gaATwO4XUTeB7AXzUB/UET+EMAsgKf8uBYlW9IPgab0SHK1Ta98CfhKqactvvUZP16f0sPpEGjuiCW/ma0FFQsa9j12f6bSOQB32lLIrOqat2wcwvyNhYhGRWlV0PL40sNrO8oqX92xGTN7t2Yu2AMxqNKhZLCrrPHC2K74Yq2OVQUNNxYWceDkrN9DpozLWgWOGwz45MiuskY/ScqpzLL7e/rPNV+XRwyS/7JWgeMGAz45cqqscVtmWa3VsWtiBpPvXsaLo5vwwnfOsiqHAmOswPHrDjXpRMXogM9yuawmJyejHgZ1WT92xPK4N6tF2JLNIqwA+NQ9q3HiZ93dOIj8oS/Ullqnoh2aqnZMLpx21yaNiEwppcpOz+OiLTmy6xhoV2Zpd0wcgz35KQdgcEAD0FmVU63V8frJWds71CxhwCdHdh0D7T4Miq1/gERBKhY0vLxjM6a/uhWlYmHZ3ahVDiOLez8Y8MmRXcdAuzLLj66xzJKCd9stK9qpGS9BPGu7bAEu2pJLVh0Du8ss9QWxfYfPorEUn/UhSi9jkLdaU+refJXFXbYAAz75oPvDoDJdRa3OlsYUDuNMffe2DR2VYQCg5QUrctIu/x0c0LD30eztsgUY8CkAWVwMo2h0z9S77ziLAxo+urbQsdfjWob3fTDgU0+MfevzIlhUql0Cx344FJTBAQ0DK1fY1tMb7zhHxo8tO0BHr9DhDJ/Ihcp0Fbv/6nQ7R7/Y2stRrdXZIoECVZtvYPqrW10/n91ZO7FKhzzjgixFxWtljV3ZcBYx4JNnXJClqGzZOOTp+XZ7SLKIAZ+IEuPQVBWV6arr59vtIcki5vDJEy//2Ij81r3g6qYpmtUekixiwCdHxoocoqjpC65ObbtpOQZ8slSZruKF75xdVtZGFCV9wdWubTcDvjkG/Izw2g+8Ml3F7r8+jcYiq3EoPFoOcNoXpS+4suTSOy7aZoB+61ut1aFw89bXLh//wnfOMthTqLScYP9Tm/HMw2stnzM4oLUnKiy59I4BPwOsbn13TsxgZPyYaeBnGofC1lhS2H/0PMp3r8arOzabllPuffT+9tcsufSOJ15lgNWJVTrj6UD6P5adEzNhDI1oGf00KmB5F9buNCSPLmxye+IVA34GjIwfc11ho+UFC4vK9gOCKGilYgEnxh6JehiJwSMOqc3s1tdKg8GeYoALr8FglU4GGFvGspae4kDLiW0/Ji68BoMz/IwYHS7hxNgjpothRGEaHNCw/6kHUGoFden6Phdeg8MZfsbos/3nDp5utzUmCoteaWNsd9B9toK+eQrgjlm/cYafQaPDJQZ7CpVd47LR4VJ7ncl4toLTXhHyjjP8lOsuW9uycQhHfnIp6mFRxrwzvt32+2yTEA7O8FPs+coZ7JqY6dhhe+DkLDdVUeicZupskxAOBvyUqkxX8frJWZZYUiw4HWzPNgnhYMBPmcp0FSPjx7BzYobBnmLDaabONgnhYA4/BYxVDnqbBKI4cZqpG/eKZL1NQpAY8BPCqmdI9yEQDPYUpsEBDUrZn3PsdqbOk6mCx4CfAFYn+0y+exlvnHqPJZYUCWNNvXFCsqqgQQSozTc4U48ZNk9LAC/Nz4jCUCxo2PfY/QzkMcHmaSnC0jSKm+sLDsdSUSwxpRNTxlvknAjTNhQr3BSVTIHP8EXksyJyXkTeFpGxoK+XBt1HEjLYUxzxzjN5Ag34IpIH8BcAPgfgPgBPi8h9QV4zDcy2mRPFDTdFJU/QM/yHALytlPq5UuoGgG8CeDzgayYeZ04Ud9wUlUxBB/wSgPcMX7/feoxscOZEcWbV9ZLiL+hF2+6zDYCuvUEi8iyAZwFg7dq1AQ8nGXZv29BRdw84nxBEFDSeM5t8Qc/w3wewxvD1XQAuGp+glHpNKVVWSpWHhoYCHk4yjA6X8NITm1AqFtp9xHc8tMbx54iCwhROOgQd8H8E4F4RWS8iKwH8HoDDAV8z8czaKPzNafawp2gwhZMegaZ0lFILIvLHAI4CyAP4S6XU2SCvmXRWbRRYtUNRYBonXQLfeKWU+i6A7wZ9naQwzt6LrcZTH9Zv9hyxOvmHKGxaXpjGSRnutA1R9+zdePJUtVbHLvawpxDlBLCqA8gJsP8LDzCNkzLspRMipw1VdsF+cECDljcreiLypljQ8OqOzfj5S9vx6o7NpgePvPzFzQz2KcQZfoj66XhZm29w9k99KWg5vPXvPtfxGA8eyRYG/BDl+2iCxmBP/Xrpid8yfZwHj2QHUzohYhM0isrggMagTgz4YSqxZQJFQD+ZiogpnQB1b6DasnEIh6aqLLOkQNz78dvw87n5jjvJEnPyZMAZfkC6e9pXa3V849Qsgz35bnBAwzMPr8X7V651BHu9HQKDPekY8ANiVoLJ3mfkt7wIpr+6FcfPzZlu2Nt/9HxEI6M4YsAPCHvaUxj0Gb3V7xt/D8mIAT8g7GlPYdALAax+3/h7SEYM+AHZspGtnilYguba0Mj4MWzZOGS6Y5a9cMiIAT8gx8/NRT0ESjl9Sahaq+PQVBVPPljqOEOBLY2pG8syA8LcKYWp3ljE8XNzbGVMtjjDDwhzpxQ2TjLICWf4Lpltojp+bs60r/2WjUO4en0h6iFTSln1ZOIkg5xwhu+C2SaqAydn219fmW+gVm90fK9Wb3S8xuCAhmJBi2L4lEB5abbC7m6IXdDyePqTa7hASz1hwHfBqY+9GwMrV2DfY+xnQs4KWh7//osP4ML4dryyY/OyhdgXRzctO+SeC7TkhqgYdXAsl8tqcnIy6mEsS9/008feaHBAw/XGIuYbS768HiXfhfHtpofWM3iTFyIypZQqOz2POfwuZoeI+8V4pCHRbSubaRn2o6ewMOB38SN9Q+QknxN87Xc3AVh+R8kZPgWFAb8LS9soSAJ0BHWzO8o9b54BAAZ98h0Dfpd+cvYCoDigMXVDpkrFwrKNUWZ3lHqXSwZ88hurdNC8pR4ZP4b1Y0cwf2MBWq67GM6dO4sF7H30/mUlc0RWZZPscklhynzA766xvzLfAAQoFrR2yZsbBS2PLRuH2jM26e0zg1KoWNAsyybZ5ZLClPmAb3ZL3VhUuO2WFXhnfDtOjD1iuWEqL9L+ULhr8Nb2ZiwAiFG1K0XstltWWKZndm/bwE1UFJrM5/Cdbqkr01VcvWHeJmFRKZSKBQyszOHvP7ga2Bgp2ezSM/oHAat0KAyZD/hWi7T6LfX+o+fRWLServtZp0/JJbjZrribU3qGdfgUlsyndJxuqbl4Rk7sgj3TMxQnmQ/4o8Ml274kq9jwjCzovy92yzXscUNxkvmUDmB9S22Xv6fs0vKC/V94oP07MzJ+zDS1VyoWOn6vuKOWopb5Gb4dp/w9ZYOWEwwO3CzTNQZ7wF2ljVmL7T1vnkFluhrSn4KIM3xbzN9nV6lYcD0Td1Npwx21FAcM+Db8bI1M8TJyz2pc+EXdMhXj9WxYp0ob7qilOGBKx4bZrTqlw4Vf1E3/fnMALn1Yx7qxI7hnz3fxfOWML9fjjlqKAwZ8G3oFz+AAK3XS5mKtvqxCq6DlsARgqbVss6gUDpyc9SXoc0ctxQEDvoPR4RIGVjLzlTb6zHp0uIQTY4/gnfHtuLFgvkD/xqn3+r6eU/kvURgyFcm8lsXpz3fK49+2Mo8bC0toLLGiJwmMM2vj74TV396iT42RuKOWotbXDF9EnhKRsyKyJCLlru/tEZG3ReS8iGzrb5j981oWZ3y+k/kbi/jYrZn67EwMvWlpvtW+1Diz7v6dsJJn61NKiX6j1E8BPAHgvxgfFJH7APwegPsB3AngByLyG0qpyM4O9FoW5+WoQ1bzxIfe5qBkcwenn3/g9u/s6U+u8XeQRBHpK+Arpd4CAFk+A3ocwDeVUtcBvCMibwN4CMDf9XO9fngti/NSLsdgHx96sLcqq+w+UtBOXgRPf3INXhzd5PMoiaIRVB6iBOCk4ev3W49Fxqkrpk7P6TIbHz/FgoZa3fn4SLsPazd3br3U4RMlgWMOX0R+ICI/Nfnf43Y/ZvKYaQwVkWdFZFJEJufm5tyO2zOv298pXooFDTN7t+LVHZsdc+p2te1Od24slaQ0c5zhK6V+u4fXfR+AMfF5F4CLFq//GoDXAKBcLvsysbarxvG6/Z3iQY/x+t+XVVpGywuuXl/A+rEjpn/Hdustdnl/ojQIKqVzGMA3RORlNBdt7wXwfwK6VofuHG21VsfOiRnsO3wWn3/gjo7nTr57ueMDgDP7+KrN30zlGD+8q7U68iJYVAqDAxo+urbQTvvolVjGn9m9bcOyD4uClmdNPGWCqD5qjEXkdwH8RwBDAGoAZpRS21rf+wqAPwCwAGCnUupvnV6vXC6rycnJnscDWLeqdcPuIAuKlpu8ul2bYuPPsk0xpY2ITCmlyk7P67dK51sAvmXxva8B+Fo/r9+LfppRWQV7fhBEz01e3W3FFTdAUValrrVCEM2oGOyjVSxorgI0G5QR2UtdwGeHy+Rx2se677H7Xb0OG5QR2UtdwO+nw6VV4Bkc0PghEhAB8M74dpQsZuFuZ/cAG5QROUllAxg9R9u9OLdl4xCOn5uz/frQVHVZBcfeR5szzH2Hz7ra+EPu6ekWq+oZt7N7HfPzRNZSGfB1vfzjL9+9elkFx+S7l/HGqfewqBQXcHtg9Z4Z0y1u9kkQUX9SHfB70f0h8XzlDA6cnG1/zWDvncLNoJ+TmweM3LKiM6PI2TlRsFKXw/ebH4dfZEWxoFmunSg010JuWXFzLaRWb9i2qCYif3GGD+uNOJXpqm+HX6SdAJjZuxUAsH7siOmd0JX55esfdi2qichfmQ/4Zq0Y9rx5BpPvXsahKc483TLWunttU9HPZjkici/zKR2rg1EOnJxlIzUPtmwcav+3VT18sWCe7uHGKKJwZH6Gz9mlPbdVScfP3WxtbVVxAyzvcsmNUUThyXzAZ5fM5XICKAXLvQlmvPSrYeklUTQyH/DNNvxY0XKClStyuHoj3akepZq7X3XGvQm5Vivibm7TMiy9JIpO5gN+d/rBKqABwI6H1uD4uTlcvdHfHYGWF0ABjaV4VgB1B29jkDY7E5ZpGaJkSEXA77e/uVNA0zmlNvI2HxaDAxpq8w0UBzQo1axB159fLGgQMS9bDJuWF9vgzR2xRMmV+IBvVVYJoKcgpP/McwdPLwve9caiZVAvFQu2C8C1+QY+dc9q/Hj2w/ZYF5Vq94sZHS5h+M+/5zroB9HiYXBAw95H73d835iWIUqmxJdlWpVV7j96vufXHB0uYclipq4HaSM9pbHKouwQaAbnEz+7bDtWp2Bf0PJ4dcdmXBjfjld2bG53mOzu8unUbtjqNae/upWBnCjFEh/w3Z5y5JXVIqTecre7BS8AXL2x0NO1Ltbqju0Fulv9jg6XcGLskY7gr4/nSw+vhZZzDvt5EbYPJsqQxKd0rMoq+93MY9WuV89XdwfJzS98D43F3pIsxQGtnYayYneeq9l4ynevdmznvKQUgz1RhiR+hh/UKUdeDtOoTFdd98k3m3fX5hu2i8FWh4PYGR0uYWbvVlywOVyEO1yJsiXxM3y3VSO9VPK4XZx0u16g5QU7PrEGR35yqSNfb3dfYPXh5eXPY3e3QkTZkfiADzgHZq+VPF4/HFyvF6hmquX4uTlX1ThWOXavfx6WUhIRAIiKUfvfcrmsJicnfX/dkfFjpnn+UrGwLDdutbHIbnHT6vXN6OWbTu+63TW9/HmIKP1EZEopVXZ6XuJz+G54qeTppcxz97YNrksh9Rm2mbyIq8O3g6pMIqJ0S0VKx4lTJY8xhWM187YLpqPDJeycmHE9FqucutsSyaAqk4go3TIxw7er5NFTOFWHNItTMHVTSaPlpJ07d1sBZCaoyiQiSrdUzPCdFlntFi1Hxo85dsp0E0zddN382K0rOjZO9bpoykVYIupF4gO+24oVqwBrl6oRwFMJJ9AMwlYLuLUemqNZfZixnw0ReZX4gG+3yNpPPtyq4sXubkIPwlZVNF5z7H43hiOibEt8Dr/fihUv+fDufL8egLv74Lh5zcp0FSPjx7B+7AhGxo+Z9tIJojEcEWVX4gO+1azZywlMbhdQ3QZgp9d0+8HB8ksi8lPiUzp+tA1wmw/3EoCdznR1k4Zi+SUR+SnxM/x+Sxy96PduQuf2g4Pll0Tkp8TP8IHwTmDyqwmZ25k7yy+JyE+pCPhh8SsAe/ngYPklEfmFAd8jPwIwZ+5EFAUG/Ihw5k5EYUv8oi0REbnDgE9ElBEM+EREGcGAT0SUEQz4REQZEaszbUVkDsC7Pr3c7QD+0afXSjO+T+7wfXKP75U7fr5PdyulhpyeFKuA7ycRmXRzqG/W8X1yh++Te3yv3InifWJKh4goIxjwiYgyIs0B/7WoB5AQfJ/c4fvkHt8rd0JrcbbAAAACgUlEQVR/n1Kbwyciok5pnuETEZFBJgK+iPypiCgRuT3qscSRiOwXkXMi8hMR+ZaIFKMeU5yIyGdF5LyIvC0iY1GPJ45EZI2IHBeRt0TkrIj8SdRjijMRyYvItIj8TZjXTX3AF5E1AP4lgNmoxxJj3wfwz5RSvwXg/wLYE/F4YkNE8gD+AsDnANwH4GkRuS/aUcXSAoDnlFK/CeBhAH/E98nWnwB4K+yLpj7gA3gFwL8BwMUKC0qp7ymlFlpfngRwV5TjiZmHALytlPq5UuoGgG8CeDziMcWOUuqSUurHrf/+FZrBjP2/TYjIXQC2A/hvYV871QFfRB4DUFVKnY56LAnyBwD+NupBxEgJwHuGr98HA5ktEVkHYBjAqWhHEluvojkJXQr7wok/AEVEfgDg102+9RUAfwZga7gjiie790kp9e3Wc76C5q3562GOLebE5DHeLVoQkY8BOARgp1Lql1GPJ25E5PMAPlBKTYnIp8O+fuIDvlLqt80eF5FNANYDOC0iQDNN8WMReUgp9f9CHGIsWL1POhH5MoDPA/iMYq2u0fsA1hi+vgvAxYjGEmsioqEZ7F9XSr0Z9XhiagTAYyLyOwBuBfBPReSAUuqZMC6emTp8EbkAoKyUYlOnLiLyWQAvA/gXSqm5qMcTJyKyAs2F7M8AqAL4EYB/pZQ6G+nAYkaas6qvA7islNoZ9XiSoDXD/1Ol1OfDumaqc/jk2n8C8E8AfF9EZkTkP0c9oLhoLWb/MYCjaC5EHmSwNzUC4PcBPNL6HZppzWIpRjIzwyciyjrO8ImIMoIBn4goIxjwiYgyggGfiCgjGPCJiDKCAZ+IKCMY8ImIMoIBn4goI/4/2MRZ+vRWCWIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(x, y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 批量梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta)) ** 2) / len(y)\n",
    "    except:\n",
    "        return float('inf')\n",
    "    \n",
    "def dJ(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2. / len(y)\n",
    "\n",
    "def gradient_descent(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):\n",
    "\n",
    "    theta = initial_theta\n",
    "    cur_iter = 0\n",
    "\n",
    "    while cur_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "\n",
    "        cur_iter += 1\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.36 s, sys: 620 ms, total: 1.98 s\n",
      "Wall time: 1.01 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "eta = 0.01\n",
    "theta = gradient_descent(X_b, y, initial_theta, eta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 2.99291217,  4.00499704])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 随机梯度下降法\n",
    ">无需指定学习率，每次计算一个随机点，通过方法计算得到学习率.**可以大大提高训练速度**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_sgd(theta, X_b_i, y_i):\n",
    "    return 2 * X_b_i.T.dot(X_b_i.dot(theta) - y_i) * 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sgd(X_b, y, initial_theta, n_iters):\n",
    "    # 下面是两个经验值，仅供参考\n",
    "    t0 = 5\n",
    "    t1 = 50\n",
    "    \n",
    "    def learning_rate(t):\n",
    "        return t0 / (t + t1)\n",
    "    \n",
    "    theta = initial_theta\n",
    "    for cur_iter in range(n_iters):\n",
    "        rand_i = np.random.randint(len(X_b))\n",
    "        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])\n",
    "        theta = theta - learning_rate(cur_iter) * gradient\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 440 ms, sys: 0 ns, total: 440 ms\n",
      "Wall time: 444 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "theta = sgd(X_b, y, initial_theta, n_iters=m//3) # 耗时大幅降低，准确率却没有下降"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 2.96829571,  4.0002945 ])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
